package com.backpack;

import sun.nio.cs.ext.MacHebrew;

import java.util.Arrays;

/**
 * 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
 * 输入：nums = [10,9,2,5,3,7,101,18]
 * 输出：4
 * 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
 */
public class LongestIncreasingSubsequence0116_300 {
    public int lengthOfLIS(int[] nums) {
        if(nums.length <= 1) return nums.length;
        //动态规划思路
        //dp[i]含义：表示以 nums[i]结尾的最长递增子序列的长度为 dp[i];
        //返回值：返回 dp 数组中的最大值！！！！！！！注意⚠️！！！！！！！！
        int[] dp = new int[nums.length];
        int res = 0;

        //初始化,都为 1！！！！！！！！
        Arrays.fill(dp, 1);
        //递归公式
        //两层 for 循环：为了得到每个下标前（含） 的最长递增子序列
        for (int i = 1; i <= dp.length; i++) {
            for (int j = 0; j < i; j++) {
                if(nums[j] < nums[i]){
                    dp[i] = Math.max(dp[j] + 1,dp[i]);
                }
                res = Math.max(res,dp[i]);

            }
        }
        return res;
    }
}

